package org.example;

public class Main {
    public static void main(String[] args) {
        final long start = System.currentTimeMillis();
        int num = 1000000; // 定义 100 万节点，节点值从 1 开始
        int lastOneNum = -1;
        for (int i = 1; i <= 10; i++) {
            YsfNode head = InitYsfNode(num);
            lastOneNum = CalcLastOneEle(head, 3, 2);
        }
        //  lastOneNum 在循环中间我们暂时不输出
        // 根据网友反馈： 在循环中间做输出，输出命令本身可能会影响性能，所以最后只输出一次

        System.out.println("lastOneNum：" + lastOneNum);
        long costTime = System.currentTimeMillis() - start;
        System.out.printf("单次平均耗时：%d ms\n", costTime / 10);
    }

    static YsfNode InitYsfNode(int n) {
        //易错点：
        // head 头元素必须要单独创建，不能放在for循环，避免head节点跟着游标节点的指针一起跑
        YsfNode head = new YsfNode(1, null);

        YsfNode cursorNode = head;

        for (int i = 2; i <= n; i++) {
            YsfNode temp = new YsfNode(i, null);

            cursorNode.number = i;
            cursorNode.next = temp;
            cursorNode = temp;
        }

        // 约瑟夫环形，必须将最后一个元素的指针指向head，这样才能形成环形
        cursorNode.next = head;

        return head;
    }

    // 根据规则不断拆除节点，计算出最后剩余的节点即可
    static int CalcLastOneEle(YsfNode head, int startNum, int step) {
        YsfNode preNode = null;
        YsfNode cursorNode = head;
        // 寻找起步元素对应的指针
        while (cursorNode != cursorNode.next) {
            if (cursorNode.number == startNum) {
                //fmt.Println("找到指定的起始元素：", startNum)
                break;
            }
            cursorNode = cursorNode.next;
        }

        //  根据规则
        while (cursorNode != cursorNode.next) {
            //  注意 ：  i <step ，就是step的起始元素包括开始元素本身，
            //  如果 i<= step  ，说明从开始元素的下一个元素算 step 的个数
            for (int i = 1; i < step; i++) {
                preNode = cursorNode;
                cursorNode = cursorNode.next;
            }
            // 拆环，通过指针的重新指向修改环形队列元素
            preNode.next = cursorNode.next;
            // 这里我们不主动调用 runtime.Gc 释放 cursorNode 指向的内存空间
            // 被删除的前一个元素的 next 重新指向下一个节点
            cursorNode = preNode.next;
        }
        return cursorNode.number;
    }
}

class YsfNode {
    public int number;
    public YsfNode next;

    public YsfNode(int number, YsfNode next) {
        this.number = number;
        this.next = next;
    }
}